package myArray;

import java.util.ArrayList;


class TupElem<E>                //三元组元素类
{
    int r;                    //行号
    int c;                    //列号
    int d;                    //元素值

    public TupElem(int r1, int c1, int d1)    //构造方法
    {
        r = r1;
        c = c1;
        d = d1;
    }
}


public class TupClass        //三元组表示类
{
    int rows;            //行数
    int cols;            //列数
    int nums;            //非零元素个数
    ArrayList<TupElem> data;    //稀疏矩阵对应的三元组顺序表

    public TupClass()        //构造方法
    {
        data = new ArrayList<TupElem>();
        nums = 0;
    }

    public void reateTup(int[][] A, int m, int n) //由二维数组A创建三元组表示data
    {
        rows = m;
        cols = n;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                if (A[i][j] != 0)        //只存储非零元素
                {
                    data.add(new TupElem(i, j, A[i][j]));
                    nums++;
                }
        }
    }


    public boolean setvalue(int i, int j, int x) { //执行A[i][j]=x
        int k = 0;
        if (i < 0 || i >= rows || j < 0 || j >= cols) return false;                //下标错误时返回false
        while (k < nums && i > data.get(k).r) k++;                    //找到第i行
        while (k < nums && i == data.get(k).r && j > data.get(k).c) k++;                    //在第i行中找到第j列
        if (data.get(k).r == i && data.get(k).c == j) //若存在该非0元素
            data.set(k, new TupElem(i, j, x));    //修改k下标元素值
        else                        //不存在该元素时插入一个元素
        {
            data.add(k, new TupElem(i, j, x));    //在下标k位置插入新元素
            nums++;
        }
        return true;                //赋值成功时返回true
    }


    public int getValue(int i, int j)        //执行x=A[i][j]
    {
        int k = 0;
        if (i < 0 || i >= rows || j < 0 || j >= cols) return 0;                //下标错误时返回0
        while (k < nums && data.get(k).r < i) k++;                    //找到第i行
        while (k < nums && data.get(k).r == i && data.get(k).c < j) k++;                    //在第i行中找到第j列
        if (data.get(k).r == i && data.get(k).c == j) //找到该非0元素
            return data.get(k).d;            //返回非0元素值
        return 0;                    //没有找到返回0
    }


    public void dispTup()            //输出三元组表示
    {
        if (nums <= 0) return;        //没有非零元素时返回
        System.out.printf("行数=%d,列数=%d,非0元素个数=%d\n", rows, cols, nums);
        for (int i = 0; i < nums; i++)
            System.out.printf("%5d%5d%5d\n", data.get(i).r, data.get(i).c, data.get(i).d);
    }

}
